---
title: "L2-051 满树的遍历"
created: 2025-11-28
tags:
  - 算法
---

# L2-051 满树的遍历

## 题目 [L2-051 满树的遍历](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1781658570803388426&page=1)

![[image-644e8e22.png]]

## 思路分析

![[image-03fd8efe.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

int root;
vector<vector<int>> tree;
vector<bool> visited;
vector<int> ans;

void dfs(int root){
	ans.push_back(root);
	visited[root]=true;
	for(auto node:tree[root]){
		if(!visited[node]){
			dfs(node);
		}
	}
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	tree.resize(n+1);
	visited.resize(n+1,false);
	for(int i=1;i<=n;i++){
		int fa;cin>>fa;
		if(fa==0)	root=i;
		tree[fa].push_back(i);
	}

	int MaxChildNum=-1;
	set<int> du;
	for(int i=1;i<=n;i++){
		int CurChildNum=tree[i].size();
		MaxChildNum=max(MaxChildNum,CurChildNum);
		if(CurChildNum>0) {
			du.insert(CurChildNum);
		}
	}

	cout<<MaxChildNum<<" ";

	// 可能存在度全为0的节点
	if(du.size()==0 || du.size()==1)	cout<<"yes"<<endl;
	else	cout<<"no"<<endl;

	dfs(root);

	cout<<ans[0];
	for(int i=1;i<n;i++)	cout<<" "<<ans[i];

	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[multimap多值查询|multimap多值查询]] 🏠 [[00-天梯赛]] ➡️ [[L2-052 吉利矩阵|L2-052 吉利矩阵]]